package com.company.ljh.medium;
/**
 * 994.腐烂的橘子
 * 在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
 * <p>
 * 值 0 代表空单元格；
 * 值 1 代表新鲜橘子；
 * 值 2 代表腐烂的橘子。
 * 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
 * <p>
 * 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/rotting-oranges
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

import java.util.*;

/**
 * @description:
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2022/5/31 16:07
 * @version:1.0
 */
public class 腐烂的橘子 {
    /**
     * 思路：广度优先遍历，注意要小心新鲜橘子无法变成腐烂橘子的情况，因此需要记录新鲜橘子变为腐烂橘子的数量和新鲜橘子的数量是否一致
     *
     */
    public int orangesRotting(int[][] grid) {
        /**广度优先遍历，将所有1变为2 */
        //广度优先遍历，先将0附近的1全部标记，然后计算1附近的1，直到实现全部标记，每一次全部标记，保存最大值
        Queue<int[]> queue = new LinkedList();
        int freshSize = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j, 0});
                } else if (grid[i][j] == 1) {
                    freshSize++;
                }
            }
        }
        int result = 0;
        while (!queue.isEmpty()) {
            int[] data = queue.poll();
            int i = data[0];
            int j = data[1];
            int size = data[2];
            result = Math.max(result, size);

            //遍历四周
            if (i > 0 && grid[i - 1][j] == 1) {
                grid[i - 1][j] = 2;
                freshSize--;
                queue.offer(new int[]{i - 1, j, size + 1});
            }
            if (i < grid.length - 1 && grid[i + 1][j] == 1) {
                grid[i + 1][j] = 2;
                freshSize--;
                queue.offer(new int[]{i + 1, j, size + 1});
            }
            if (j > 0 && grid[i][j - 1] == 1) {
                grid[i][j - 1] = 2;
                freshSize--;
                queue.offer(new int[]{i, j - 1, size + 1});
            }
            if (j < grid[0].length - 1 && grid[i][j + 1] == 1) {
                grid[i][j + 1] = 2;
                freshSize--;
                queue.offer(new int[]{i, j + 1, size + 1});
            }
        }
        if (freshSize > 0)
            result = -1;
        return result;

    }
}